import java.util.Arrays;

/**
 * @author TrinhNX
 * 04/18
 */
public class Euler023 {
	public static void main(String[] args) {

		final int MAX = 28123;
		/*
		 * Ý tưởng: Khởi tạo từ 1-MAX
		 * 1. Liệt kê tất cả các abundant number
		 * 2. Khởi tạo 1 mảng MAX phần tử, giá trị là (index+1)
		 * 3. Lặp theo kiểu buble mảng abudant, cộng từng cái lại với nhau
		 *  -> Nếu như cái giá trị đó < MAX => số này ko thỏa mãn => set lại là 0
		 * 4. Mảng gồm các số ko là abudant và 0 *là các số abudant*
		 * 5. Tính tổng thôi.
		 */
		final int[] source = new int[MAX]; // Mảng chứa số + số là abudant (0)
		final int[] data = new int[MAX];
		long start = System.currentTimeMillis();
		System.out.println("START");
		// Initialize the data
		for (int num = 1; num <= MAX; num++) {
			// Get the sum of divisor of number
			int sum;
//			for (int j = (num / 2); j >= 2; j--) {
//				if (num % j == 0)
//					sum = sum + j;
//			}
//			sum = (sum > num && sum < MAX) ? num : 0;
			// Tất nhiên, nếu gọi làm => slower hơn, từ 1149 đến 1439 s
			// Thử làm theo cách mới 
			// int sum = numOfDivisor(num);
			// int sum = numOfDivisor1(num);
			// If sum > number and not reach the limit 
			// well, abudant here, else, reset it 0 :lol:
			
			// Wow, nhanh gap 10 lan :v
			sum = (isAbudant(num) ? num : 0);
			data[num - 1] = sum; // Create the data
			source[num - 1] = num; // Create the db
		}
		// Sort the list 
		Arrays.sort(data);
		// Find the first not zero element
		int index_lower = 0;
		for (int i = MAX - 1; i >= 0; i--) {
			if (data[i] < 1) {
				index_lower = i + 1; // +1 vì thằng index :D
				break;
			}
		}
		// Ok, giờ gán tất cả những thằng được tạo từ tổng 2 số abudant là 0
		for (int i = index_lower; i < MAX; i++) {
			for (int j = i; j < MAX; j++) {
				try {
					source[data[i] + data[j] - 1] = 0;
				} catch (IndexOutOfBoundsException e) {
					// Vì là sort, nên nếu exception, ko cần tính tiếp, next luôn :v
					// Cái này sẽ tăng speed lên 90 lần :v (từ 91746 xuống 1149)
//					System.out.println("Exception value: " + data[i] + "\t: " + data[j]);
					break;
				}
			}
		}

		// Sum all
		int sum = 0;
		for (int i = 0; i < MAX; i++) {
			sum += source[i];
		}
		System.out.println(sum);
		System.out.println("END AFTER " + (System.currentTimeMillis() - start));
	}
	
	// TrinhNX 04/18
	// Check a number is an abudant or not
	private static boolean isAbudant(int num) {
		int sqrt = (int)Math.sqrt(num);
		int sum = 1;
		for (int i = 2 ; i <= sqrt ; i++)
		{
			if (num % i == 0)
			{
				sum += i + (num / i == i?0:num/i);
			}
			if (sum > num)
			{
				return true;
			}
		}
		return sum > num;
	}

	/**
	 * Sum of divisor (less than num)
	 * @param num
	 * @return
	 */
	private static int numOfDivisor(final int num) {
		int sum = 1;
		for (int i = (num / 2); i >= 2; i--) {
			if (num % i == 0)
				sum = sum + i;
		}
		return sum;
	}

	// http://mathschallenge.net/library/number/sum_of_divisors
	// http://math.stackexchange.com/questions/22721/is-there-a-formula-to-calculate-the-sum-of-all-proper-divisors-of-a-number
	static int numOfDivisor1(int num) {
		// Phân tích ra các thừa số nguyên tố.
		int result = 1;
		if (num > 3) {
			int i = 2;
			do {
				if (num % i == 0) {
					num = num / i;
					System.out.println(i);
				} else {
					i = i + 1;
				}
			} while (i <= num);
		}
		
		return result;
	}
	
}
